package bin_tree.oj;

public class Num105 {
    int index = 0;
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        return buildTreeInternal(preorder,inorder,0,inorder.length);
    }

    /**
     * 根据前序遍历结果的数组和中序遍历结果的数组，及部分区间，递归构建二叉树
     * @param preOrder 前序遍历结果
     * @param inOrder 中序遍历结果
     * @param left
     * @param right
     * @return
     */
    private TreeNode buildTreeInternal(int[] preOrder, int[] inOrder, int left, int right) {
        if (left >= right){
            return null;
        }
        if (index >= preOrder.length){
            return null;
        }
        TreeNode root = new TreeNode(preOrder[index]);
        index++;
        int pos = find(inOrder,left,right,root.val);
        root.left = buildTreeInternal(preOrder,inOrder,left,pos);
        root.right = buildTreeInternal(preOrder,inOrder,pos+1,right);
        return root;
    }

    //在中序遍历中找到当前节点的位置，确定其左子树右子树范围。
    private int find(int[] inOrder, int left, int right, int val) {
        for (int i = left; i < right; i++) {
            if (inOrder[i] == val){
                return i;
            }
        }
        return -1;
    }
}
